package two.divide;

import java.util.ArrayList;
import java.util.List;

/**
 *  括号生成
 *  时间复杂度：O(ans)
 *  思路：分治（着眼于第一段子问题）
 *  划分子问题标准：第一个子问题，作为不可分割的整体
 *  分割方法：(a)b
 *  (a)：k对括号，子问题a是k-1对括号
 *  b：n-k对括号
 */
public class GenerateParenthesis {

    public List<String> generateParenthesis(int n) {
        //边界条件
        if(n == 0){
            List<String> temp = new ArrayList<>();
            temp.add("");
            return temp;
        }
        List<String> ans = new ArrayList<>();
        //本层逻辑
        for(int k = 1; k <= n; k++){ //不同k之间加法原理
            List<String> result_a = generateParenthesis(k - 1); //子问题
            List<String> result_b = generateParenthesis(n - k);
            for(String a : result_a){ //左右两个子问题：乘法原理
                for(String b : result_b){
                    ans.add("(" + a + ")" + b);
                }
            }
        }
        return ans;
    }
}
